// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-12 10:31
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Intervalsummation;

import java.util.TreeMap;
import java.util.TreeSet;

public class isCovered {
    public isCovered() {
        root = buildTree(1, 50);
    }

    //2 线段树
    public boolean isCovered(int[][] ranges, int left, int right) {
        for (int[] range : ranges) {
            update(range[0], range[1]);
        }
        int tot = right - left + 1, cnt = query(left, right);
        return tot == cnt;
    }

    public Node root;

    /*-----线段树节点构造-----*/
    class Node {
        int start, end;
        int value, lazy;
        Node left, right;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }


    public Node buildTree(int left, int right) {
        Node node = new Node(left, right);
        if (left == right) {
            return node;
        }
        int mid = left + ((right - left) >> 1);
        node.left = buildTree(left, mid);
        node.right = buildTree(mid + 1, right);
        return node;
    }

    public void update(int left, int right) {
        if (left > right) {
            throw new IllegalArgumentException("Area Exception!");
        }
        update(this.root, left, right);
    }

    public void pushDown(Node root) {
        // lazy 和当前层的数值没有关系，和下一层的数值有关
        if (root == null || root.start == root.end) {
            return;
        }
        int mid = root.start + root.end >> 1;
        /*
            push 的value 取值出现问题，+= 和 = 都不适合，= 小区间的值会对大区间值进行覆盖，+= 会重复计算区间数据
         */
        if (root.left.start == 1 && root.left.end == 25) {
            int flag = 1;
        }
        root.left.value = Math.min(mid - root.start + 1, Math.max(root.left.value, (root.lazy * (mid - root.start + 1))));
        //root.left.value = Math.max(root.left.value, (root.lazy * (mid - root.start + 1)));
        root.left.lazy += root.lazy;
        root.right.value = Math.min(root.end - mid, Math.max(root.right.value, root.lazy * (root.end - mid)));
        //root.right.value = Math.max(root.right.value, root.lazy * (root.end - mid));
        root.right.lazy += root.lazy;
        root.lazy = 0;
    }

    private void update(Node root, int left, int right) {
        if (root.start >= left && root.end <= right) {
            root.value = root.end - root.start + 1;
            root.lazy++;
            return;
        }
        int mid = root.start + root.end >> 1;
        pushDown(root);
        if (mid >= right) {
            update(root.left, left, right);
        } else if (mid < left) {
            update(root.right, left, right);
        } else {
            update(root.left, left, mid);
            update(root.right, mid + 1, right);
        }
        pushup(root);
    }

    private void pushup(Node root) {
        root.value = root.left.value + root.right.value;
    }


    public int query(int left, int right) {
        return query(root, left, right);
    }

    private int query(Node root, int left, int right) {
        pushDown(root);
        if (left <= root.start && right >= root.end) {
            // 查询区间包含当前的根节点表示的区间，返回当前根节点表示区间值的出现总次数
            return root.value;
        }
        int mid = root.start + ((root.end - root.start) >> 1), ans = 0;
        if (mid >= left) {
            // 当查询区间在当前根节点左区域存在值时，取出
            ans += query(root.left, left, right);
        }
        if (mid < right) {
            // 当查询区间在当前根节点右区域存在值时，取出
            // mid在计算的时候是偏向左边的，所有这里不取等号
            ans += query(root.right, left, right);
        }
        return ans;
    }

    public static void main(String[] args) {
        // int[][] ranges = {{1, 1}};
        int[][] ranges = {{25, 42}, {7, 14}, {2, 32}, {25, 28}, {39, 49}, {1, 50}, {29, 45}, {18, 47}};
        int left = 15, right = 38;
//        int[][] ranges = {{1, 2}, {3, 4}, {5, 6}};
//        int[][] ranges = {{1, 10}, {10, 20}};
//        int left = 1, right = 20;
        isCovered ic = new isCovered();
        System.out.println(ic.isCovered(ranges, left, right));
    }


}
////    //1  插旗法
////    public boolean isCovered(int[][] ranges, int left, int right) {
////        TreeMap<Integer, Integer> map = new TreeMap<>();
////        for (int[] range : ranges) {
////            if (range[0] == range[1]) {
////                map.put(range[0], map.getOrDefault(range[0], 0) + 1);
////            } else {
////                map.put(range[0], map.getOrDefault(range[0], 0) + 1);
////                map.put(range[1], map.getOrDefault(range[1], 0) - 1);
////            }
////        }
////        if (left == right) {
////            return map.getOrDefault(left, 0) != 0;
////        }
////
////        map.put(left, map.getOrDefault(left, 0) + 1);
////        map.put(right, map.getOrDefault(right, 0) - 1);
////        int sum = 0;
////        for (Integer integer : map.keySet()) {
////            sum += map.get(integer);
////            if (sum > 1) {
////                return true;
////            }
////        }
////        return false;
////    }
